﻿/**
 * @file list.c
 * @author septem (jsm920@outlook.com)
 * @brief @see list.h
 * @version 0.1
 * @date 2024-12-09
 * 
 * @copyright Copyright (c) 2024
 * 
 */
#include "list.h"

#if defined(_WIN32) && defined(_MSC_VER)
// #pragma execution_character_set("utf-8")
#define WIN32_LEAN_AND_MEAN // 预处理器宏定义，它告诉编译器仅包含Windows SDK中最常用的函数和数据类型，从而减小编译时间和生成的可执行文件大小。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#elif defined(__linux__)
#include <stdio.h>
#include <stdlib.h> //malloc() realloc() free()
#include <string.h> // memset() memcpy() memmove()
#include <assert.h> // assert()
#endif

listiterator_t* ListIteratorInit2(listiterator_t* pli, list_t* pl, int ser)
{
    if(ser > (int)pl->cntElem || pl->cntElem == 0)
    {
        return NULL;
    }
    else if(ser < 0)
    {
        ser =  (int)pl->cntElem + ser;
        if(ser < 0)
        {
            return NULL;
        }
    }
    pli->pl = pl;
    pli->ser = (unsigned int)ser;
    listnode_t* _pln = pl->plnHead;
    for(int i = 0; i != ser; i++)
    {
        _pln = _pln->plnNext;
    }
    pli->pln = _pln;
    return pli;
}

listiterator_t* ListIteratorPrev(listiterator_t* pli)
{
    if(pli->pln->plnPrev)
    {
        pli->pln = pli->pln->plnPrev;pli->ser--;
        return pli;
    }
    return NULL;
}

listiterator_t* ListIteratorNext(listiterator_t* pli)
{
    if(pli->pln->plnNext)
    {
        pli->pln = pli->pln->plnNext;pli->ser++;
        return pli;
    }
    return NULL;
}

list_t* ListMalloc(unsigned int szElem, unsigned int cnt)
{
    if(cnt < 8) { cnt = 8;}
    unsigned int _szMem = ListMemUsed(szElem, cnt);
    list_t* _pl = (list_t*)malloc(_szMem);
    if(_pl == NULL)
    {
        return NULL;
    }
    // memset(_pl, 0, _szMem);
    if(NULL == ListInit(_pl, szElem,cnt))
    {
        free(_pl);
        return NULL;
    }
    return _pl;
}

list_t* ListInit(list_t* pl ,unsigned int szElem, unsigned int cnt)
{
    pl->cntElem = 0;
    pl->cntCapacity = cnt;
    pl->cntGrow = cnt;
    pl->szElem = szElem;
    pl->plnHead = NULL;
    pl->plnTail = NULL;
    pl->szNode = roundup((sizeof(listnode_t)+szElem), sizeof(void*));
    pl->plbM = NULL;
    pl->cntPLBM = 0;
    memset(pl->plb, 0,sizeof(listblock_t)* LISTDEFAULTCNTBLOCK ); // 最后一个用于块不够使用时 保存 malloc(n*sizeof(listblock_t))
    pl->plnPeralloc = (listnode_t*)((char*)pl + sizeof(list_t));
    listnode_t* plnPrev = pl->plnPeralloc;
    listnode_t* pln = pl->plnPeralloc;
    for(int i = 0; i != cnt; i++,pln = (listnode_t*)((char*)pln + pl->szNode))
    {
        plnPrev->plnNext = pln; pln->plnPrev = plnPrev; plnPrev = pln;
    }
    plnPrev->plnNext = NULL; pl->plnPeralloc->plnPrev = NULL;
    return pl;
}

void ListUninit(list_t*pl)
{
    for(int i = 0; pl->plb[i] !=NULL && i != LISTDEFAULTCNTBLOCK; i++)
    {
        free(pl->plb[i] ); pl->plb[i]  = NULL; 
    }
    if(pl->plbM)
    {
        listblock_t* plb = pl->plbM;
        for(int i = 0;plb[i] != NULL && i != pl->cntPLBM; i++)
        {
            free(plb[i] ); plb[i] = NULL; 
        }
        free(pl->plbM);pl->plbM = NULL;pl->cntPLBM = 0;
    }
}

void ListFree(list_t*pl)
{
    ListUninit(pl);
    free(pl);
}

int ListRealloc(list_t* pl, unsigned int grow)
{
    grow = (grow < pl->cntGrow ? pl->cntGrow: grow);
    listnode_t* _pln = malloc(pl->szNode * grow);
    if(_pln == NULL)
    {
        return -1;
    }
    if(pl->plbM == NULL) // 最后一个是用来当作 listblock_t*来用的
    {
        for(int i = 0; i != LISTDEFAULTCNTBLOCK; i++)
        {
            if(pl->plb[i] == NULL)
            {
                pl->plb[i] = _pln; 
                break;
            }
        }
        if(_pln == NULL)
        { 
            pl->plbM = (listblock_t *)malloc(sizeof(listblock_t) * LISTDEFAULTCNTBLOCK); 
            if(pl->plbM == NULL)
            {
                free(_pln);return -1;
            }
            pl->cntPLBM = LISTDEFAULTCNTBLOCK;
            memset(pl->plbM, 0, sizeof(listblock_t) * LISTDEFAULTCNTBLOCK);
            pl->plbM[0] = _pln;
        }
    }
    else
    {
        listblock_t* plb = pl->plbM;
        for(int i = 0; i != pl->cntPLBM; i++)
        {
            if(plb[i] == NULL)
            {
                plb[i] = _pln;
                break;
            }
        }
        if(_pln == NULL)
        {
            listblock_t* plbTmp = (listblock_t*)realloc(pl->plbM,sizeof(listblock_t) * (pl->cntPLBM+LISTDEFAULTCNTBLOCK));
            if(plbTmp == NULL)
            {
                free(_pln);return -1;
            }
            memset( (char*)plbTmp + sizeof(listblock_t)*pl->cntPLBM, 0, sizeof(listblock_t)* LISTDEFAULTCNTBLOCK);
            pl->plbM = plbTmp;
            pl->plbM[pl->cntPLBM] = _pln; 
            pl->cntPLBM += LISTDEFAULTCNTBLOCK;
        }
    }
    pl->cntCapacity += grow;
    listnode_t* plnPrev = _pln;
    listnode_t* pln = _pln;
    for(int i = 0; i != grow; i++,pln = (listnode_t*)((char*)pln + pl->szNode))
    {
        plnPrev->plnNext = pln; pln->plnPrev = plnPrev; plnPrev = pln;
    }
    _pln->plnPrev = NULL; 
    plnPrev->plnNext = pl->plnPeralloc ? pl->plnPeralloc->plnPrev = plnPrev,pl->plnPeralloc:NULL;
    pl->plnPeralloc = _pln;
    return 0;
}

void* ListPush(list_t*pl, void* data)
{
    if(pl->cntElem >= pl->cntCapacity && -1 == ListRealloc(pl,0))
    {
        return NULL;
    }
    assert(pl->plnPeralloc != NULL);
    listnode_t* _pln = pl->plnPeralloc; pl->plnPeralloc = pl->plnPeralloc->plnNext;//pl->plnPeralloc->plnPrev = NULL;
    void* _pdata = ListNodeData(_pln);
    if(pl->plnTail)
    {
        _pln->plnPrev = pl->plnTail; _pln->plnNext = NULL; pl->plnTail->plnNext = _pln; pl->plnTail = _pln;
    }
    else
    {
        pl->plnHead = _pln; pl->plnHead->plnNext = NULL; pl->plnHead->plnPrev = NULL; pl->plnTail = pl->plnHead;
    }
    pl->cntElem++;
    if(data)
    {
        memcpy(_pdata, data, pl->szElem);
    }
    return _pdata;
}

listnode_t* ListPop(list_t*pl)
{
    if(pl->plnTail)
    {
        pl->cntElem--;
        listnode_t* plnPrev = pl->plnTail->plnPrev; 
        listnode_t* plnTail = pl->plnTail;
        if(plnPrev)
        {
            pl->plnTail = plnPrev; plnPrev->plnNext = NULL;
        }
        else
        {
            pl->plnTail=NULL;pl->plnHead = NULL;
        }
        if(pl->plnPeralloc)
        {
            pl->plnPeralloc->plnPrev = plnTail;plnTail->plnNext=pl->plnPeralloc; pl->plnPeralloc = plnTail;pl->plnPeralloc->plnPrev=NULL;
        }
        else
        {
            pl->plnPeralloc = plnTail;pl->plnPeralloc->plnNext = NULL;pl->plnPeralloc->plnPrev = NULL;
        }
        return plnPrev;
    }
    return NULL;
}

void* ListUnshift(list_t*pl, void* data)
{
    if(pl->cntElem >= pl->cntCapacity && -1 == ListRealloc(pl,0))
    {
        return NULL;
    }
    assert(pl->plnPeralloc != NULL);
    listnode_t* _pln = pl->plnPeralloc; pl->plnPeralloc = pl->plnPeralloc->plnNext;//pl->plnPeralloc->plnPrev = NULL;
    void* _pdata = ListNodeData(_pln);
    if(pl->plnHead)
    {
        _pln->plnNext = pl->plnHead; _pln->plnPrev = NULL; pl->plnHead->plnPrev = _pln; pl->plnHead = _pln;
    }
    else
    {
        pl->plnHead = _pln; _pln->plnPrev = NULL; _pln->plnNext = NULL; pl->plnTail = pl->plnHead;
    }
    pl->cntElem++;
    if(data)
    {
        memcpy(_pdata, data, pl->szElem);
    }
    return _pdata;
}

listnode_t* ListShift(list_t*pl)
{
    if(pl->plnHead)
    {
        pl->cntElem--;
        listnode_t* plnNext = pl->plnHead->plnNext; 
        listnode_t* plnHead = pl->plnHead;
        if(plnNext)
        {
            pl->plnHead = plnNext; plnNext->plnPrev = NULL;
        }
        else
        {
            pl->plnTail=NULL;pl->plnHead = NULL;
        }
        if(pl->plnPeralloc)
        {
            pl->plnPeralloc->plnPrev = plnHead;plnHead->plnNext=pl->plnPeralloc; pl->plnPeralloc = plnHead;pl->plnPeralloc->plnPrev=NULL;
        }
        else
        {
            pl->plnPeralloc = plnHead;pl->plnPeralloc->plnNext = NULL;pl->plnPeralloc->plnPrev = NULL;
        }
        return plnHead;
    }
    return NULL;
}

listnode_t* ListInsert(list_t* pl, listnode_t* where, void* data, unsigned int cnt)
{
    assert(data != NULL && cnt != 0);
    if(pl->cntElem + cnt >= pl->cntCapacity && -1 == ListRealloc(pl,cnt)) //防止空间不足
    {
        return NULL;
    }
    assert(pl->plnPeralloc != NULL);
    listnode_t* _plnHead = pl->plnPeralloc; // 插入的第一个节点
    listnode_t* _plnTail = _plnHead; //插入的最后一个节点
    pl->cntElem += cnt;
    for(int i = 0; i != cnt - 1; i++)
    {
        if(data)
        {
            memcpy(ListNodeData(_plnTail), data, pl->szElem);
            data = (char*)data + pl->szElem;
        }
        _plnTail = _plnTail->plnNext; assert(_plnTail != NULL);
    }
    if(data)
    {
        memcpy(ListNodeData(_plnTail), data, pl->szElem);
        // data = (char*)data + pl->szElem;
    }
    pl->plnPeralloc = _plnTail->plnNext;
    if(where != NULL)
    { //插入到 where之前
        if(where->plnPrev)
        {
            where->plnPrev->plnNext = _plnHead; _plnHead->plnPrev = where->plnPrev;
        }
        else
        {
            pl->plnHead = _plnHead; _plnHead->plnPrev = NULL;
        }
        _plnTail->plnNext = where; where->plnPrev = _plnTail;
    }
    else //相当于 push操作
    {
        if(pl->plnTail)
        {
            pl->plnTail->plnNext = _plnHead;_plnHead->plnPrev = pl->plnTail;pl->plnTail=_plnTail;
        }
        else
        {
            pl->plnHead = _plnHead;pl->plnTail = _plnTail;_plnHead->plnPrev = NULL;_plnTail->plnNext = NULL;
        }
    }
    return _plnHead;
}

listnode_t* ListErase(list_t*pl,listnode_t* where, unsigned int cnt)
{
    listnode_t* _plnHead = where; // 删除的第一个节点
    listnode_t* _plnTail = _plnHead; //删除的最后一个节点
    int i = 0;
    for(; i != cnt - 1; i++)
    {
        if(_plnTail->plnNext == NULL)
        {
            break;
        }
        _plnTail = _plnTail->plnNext; 
    }
    pl->cntElem -= (i+1);
    // 从 链表移除
    if(_plnHead->plnPrev)
    {
        if(_plnTail->plnNext)
        {
            _plnHead->plnPrev->plnNext = _plnTail->plnNext;_plnTail->plnNext->plnPrev=_plnHead->plnPrev;
        }
        else
        {
            _plnHead->plnPrev->plnNext = NULL; pl->plnTail = _plnHead->plnPrev;
        }
    }
    else
    {
        if(_plnTail->plnNext)
        {
            pl->plnHead = _plnTail->plnNext; pl->plnHead->plnPrev;
        }
        else
        {
            pl->plnHead=NULL;pl->plnTail = NULL;
        }
    }
    //把删除的链表再加到 pl->plnPeralloc 这前
    if(pl->plnPeralloc)
    {
        _plnTail->plnNext = pl->plnPeralloc; pl->plnPeralloc->plnPrev = _plnTail; pl->plnPeralloc=_plnHead;_plnHead->plnPrev = NULL;
    }
    else
    {
        pl->plnPeralloc = _plnHead; _plnHead->plnPrev = NULL; _plnTail->plnNext = NULL;
    }
    return _plnTail->plnNext;
}

listnode_t* ListMoveBefore(list_t* pl,listnode_t* where,listnode_t* pln)
{
    // 先把 pln 从 队列中删除
    if(pln->plnNext)
    {
        pln->plnNext->plnPrev = pln->plnPrev;
    }
    else
    {
        pl->plnTail = pln->plnPrev;
        if( pln->plnPrev ) {pl->plnTail->plnNext = NULL;}
    }
    if(pln->plnPrev)
    {
        pln->plnPrev->plnNext = pln->plnNext;
    }
    else
    {
        pl->plnHead = pln->plnNext;
        if(pln->plnNext) {pl->plnHead->plnPrev=NULL;}
    }
    // 插入 where 之前
    if(where)
    {
        pln->plnNext = where;pln->plnPrev = where->plnPrev; where->plnPrev = pln;
        if(where == pl->plnHead) {pl->plnHead = pln;}
    }
    else
    {
        if(pl->plnTail)
        {
            pl->plnTail->plnNext = pln; pln->plnPrev = pl->plnTail;pln->plnNext = NULL;
            pl->plnTail = pln;
        }
        else
        {
            pl->plnHead = pln; pl->plnTail = pln;
            pln->plnPrev = NULL;pln->plnNext = NULL;
        }
    }
    return pln;
}

listnode_t* ListSwap(list_t* pl,listnode_t* pln0,listnode_t* pln1)
{
    assert(pln0 != NULL || pln1 != NULL);
    if(pln0 == NULL)
    {
        // 从 pln1 原有位置删除 插入 pl->plnHead
        pln0 = pl->plnHead;
    }
    else if(pln1 == NULL)
    {
        pln1 = pl->plnTail;
    }

    return pln0;
}

listnode_t* ListSearch(list_t*pl, void* ptr, int (*compar)(const void*, const void*))
{
    for(listnode_t* pln = pl->plnHead; pln; pln = pln->plnNext)
    {
        if(0 == compar(ptr, ListNodeData(pln)))
        {
            return pln;
        }
    }
    return NULL;
}

listnode_t* ListAt(list_t* pl, int pos)
{
    if(pos < 0)
    {
        pos =  (int)pl->cntElem + pos;
    }
    return ListAt2(pl, (unsigned int) pos);
}

listnode_t* ListAt2(list_t* pl, unsigned int pos)
{
    listnode_t* pln = NULL;
    if( pos >=0 && pos < pl->cntElem)
    {
        // 二分法
        if(pos < pl->cntElem/2)
        {
            pln = pl->plnHead;
            for(unsigned int i = 0; i != pos; i++)
            {
                pln = pln->plnNext;
            }
        }
        else
        {
            pln = pl->plnTail;
            for(unsigned int i = 1; i != pl->cntElem - pos; i++)
            {
                pln = pln->plnPrev;
            }
        }
    }
    return pln;
}

#ifdef _DEBUG
void list_print_positive_order_int(list_t* pl)
{
    unsigned int cnt = 0;listnode_t*ppp = pl->plnPeralloc;
    while (ppp)
    {
        cnt++;ppp = ppp->plnNext;
    }
    
    // 在 linux shell中 printf 打印\n时就会刷新输出缓存，但是在windows vscode 中必须调用 fflush(stdout); 才可以刷新输出缓存
    printf("PositiveOrder:%p-%p-%p-%u-%u-%u-%u-%u-%u\n", pl->plnHead, pl->plnTail, pl->plnTail,pl->cntCapacity, pl->cntElem, pl->cntGrow,pl->szElem,pl->szNode,cnt);
    fflush(stdout);
    int i = 0;
    for(listblock_t* plb = pl->plb; plb != NULL && plb-pl->plb!= LISTDEFAULTCNTBLOCK; plb++)
    {
        printf("%p ",plb ); fflush(stdout);
        i++; if(i > 5){printf("\n");i=0;}
    }
    if(pl->plbM)
    {
        for(listblock_t* plb = pl->plbM; plb != NULL && plb-pl->plbM!= pl->cntPLBM; plb++)
        {
            printf("%p ",plb ); fflush(stdout);
            i++; if(i > 5){printf("\n");i=0;}
        }
    }
    if(i <= 5){printf("\n");fflush(stdout);}
    for(listnode_t* pln = pl->plnHead; pln != NULL; pln = ListNodeNext(pln) )
    {
        int *pi = (int*)ListNodeData(pln);
        printf("% 6d (%p-%p-%p)\n", *pi, pln,pln->plnPrev, pln->plnNext);fflush(stdout);
    }
    printf("\n"); fflush(stdout);
}
void list_print_negative_order_int(list_t* pl)
{
    // 在 linux shell中 printf 打印\n时就会刷新输出缓存，但是在windows vscode 中必须调用 fflush(stdout); 才可以刷新输出缓存
    printf("PositiveOrder:%p-%p-%p-%u-%u-%u-%u-%u\n", pl->plnHead, pl->plnTail, pl->plnTail,pl->cntCapacity, pl->cntElem, pl->cntGrow,pl->szElem,pl->szNode);
    fflush(stdout);
    int i = 0;
    for(listblock_t* plb = pl->plb; plb != NULL && plb-pl->plb!= LISTDEFAULTCNTBLOCK; plb++)
    {
        printf("%p ",plb ); fflush(stdout);
        i++; if(i > 5){printf("\n");i=0;}
    }
    if(pl->plbM)
    {
        for(listblock_t* plb = pl->plbM; plb != NULL && plb-pl->plbM!= pl->cntPLBM; plb++)
        {
            printf("%p ",plb ); 
            i++; if(i > 5){printf("\n");fflush(stdout);;i=0;} 
        }
    }
    if(i <= 5){printf("\n");fflush(stdout);}
    for(listnode_t* pln = pl->plnTail; pln != NULL; pln = ListNodePrev(pln) )
    {
        int *pi = (int*)ListNodeData(pln);
        printf("% 6d (%p-%p-%p)\n", *pi, pln,pln->plnPrev, pln->plnNext);fflush(stdout);
    }
    printf("\n"); fflush(stdout);
}
void list_print_int_by_iterator(list_t* pl)
{
    int i = 0;
    for(listiterator_t* pli = ListIteratorInit(pl,0); pli != NULL; i++,pli = ListIteratorNext(pli) )
    {
        int*pi = ListIteratorDataPtr(pli);
        printf("% 6d ", *pi);fflush(stdout);
        if(i<9){i++;}else{printf("\n");i=0;}
    }
    if(i<10){printf("\n");fflush(stdout);} 
    printf("\n"); fflush(stdout);
}
#endif